package com.andy.note.main.sort;

/**
 * 插入排序
 * 参考文章
 * https://mp.weixin.qq.com/s?__biz=MzI4Njc5NjM1NQ==&mid=2247483824&idx=1&sn=15cdb8ac18546ae005140233ad4800bb&chksm=ebd63e9cdca1b78a7f664f7f8e3ec1760fa027f0c84427aaa2dfa4cdafa862c7b1f8ba88480b&scene=21#wechat_redirect
 * @author Andy
 *
 */
public class InsertSort {
    public void insertSort(int[] array, int first, int last) {        
    int temp, i, j;        
    for (i = first + 1; i <= last - 1; i++) {
            temp = array[i];
            j = i - 1;            
        while (j >= first && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;            // 打印每次排序结果
            for (int m = 0; m <= array.length - 1; m++) {
                System.out.print(array[m] + "\t");
            }
            System.out.println();
        }
    }    
     public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
            int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        insertSort.insertSort(array, 0, array.length);      
             for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
    }
}
